A network communication protocol uses error detection codes to protect data from corruption. The transmitter calculates parity bits and appends the parity bits to a block of data which is transmitted to a receiver. The receiver recalculates the parity bits based on the information it receives. Only if the received and receiver calculated parities are identical is the received block of data assumed to be error free. The code used to calculate the parities determines how well the information is protected and how easy it is to calculate the parities.
FIG. 1 shows a typical communication system 10. The transmitter 12 appends an h-bit parity word P to a k-bit data word Q to form a redundant codeword R. The parity word P is calculated using a particular error correction code. The redundant codeword R is transmitted via channel 14 to a receiver 16. The redundant codeword R may be corrupted in the channel 14 due to noise or other reasons. Thus, the codeword that is received at the receiver 16 is designated R*.
The received codeword R* may be viewed as being formed by the polynomial addition of R and an error polynomial E. The error polynomial E has non-zero terms in those bit positions where there is an error. Because R is a valid codeword and polynomial addition is linear, R* will be a valid codeword only if the error polynomial E is also a valid codeword. Thus, an error will be detected at the receiver as long as the error polynomial E is not also a valid codeword. FIG. 2 shows the binary representation of Q, P, R and E.
For some error detection codes, the k-bit data word Q is divided into a plurality of h/2-bit symbols, each of which is labeled Q.sub.i. Similarly, the transmitted redundant codeword R may be divided into h/2-bit symbols labeled R.sub.i. In this case, the parity word P is divided into two h/2-bit symbols, the top half parity symbol P.sub.1 and the bottom half parity symbol P.sub.0. FIG. 3 shows the binary representations of P.sub.0, P.sub.1 and Q.sub.i.
There are four error detection parameters which may be utilized in characterizing the error detection capabilities of an error detection code. These parameters are:
h--numbers of redundant (i.e. parity) bits PA1 k--maximum number of message bits that can be protected using h parity bits PA1 d--minimum number of bits that must be changed to make any codeword of (h+k) bits into any other codeword PA1 b--maximum error burst length that is always detected, e.g. if an error changes bits 11, 13 and 15, the burst length is five. PA1 d large as possible to detect all small errors PA1 b large as possible to detect a large single block of errors PA1 k large as possible to allow large error detection blocks PA1 d=4 PA1 b=h PA1 k=2.sup.h PA1 d=4 PA1 b=h PA1 k=(h/2).times.(2.sup.h/2 -1)
The number of parity bits h is the key parameter for an error detection code because the chance of a random error resulting in the correct parities is at least 2.sup.-h. An error detection code with distance d guarantees detecting all errors which change less than d bits in a block of k bits.
Typically, the number of parity bits h is fixed by the application requirements. Once h is fixed, the three remaining parameters used to describe the error detection capabilities should be as follows:
There are a number of error detection codes disclosed in the prior art. However, the prior art error correction codes have certain shortcomings. For example, the well known CRC (Cyclic Redundancy Code) has very strong error detection characteristics. However, the CRC requires data to be processed in the originally transmitted order. In addition, some embodiments of the CRC code are very slow when implemented in software. The CRC code is disclosed in W. W. Peterson et al., "Cyclic Codes for Error Detection," Proceedings of the IRE, pp. 228-235, January 1961. Another prior art error detection code is the Fletcher Checksum. The Fletcher Checksum can be implemented efficiently in software but has weaker error detection capabilities than CRC and still requires perfectly ordered data. The Fletcher Checksum is disclosed in J. G. Fletcher, "An Arithmetic Checksum For Serial Transmissions," IEEE Transactions on Communications, Vol. COM-80, No. 1, pp. 247-252, January 1982. The TCP (Transmission Control Protocol) offers efficient software implementation and out of order processing, but it has even weaker error detection properties. The TCP is disclosed in Department of Defense, "Transmission Control Protocol," MIL-STD-1778, May 1983. Another error detection code known as XTP CXOR is disclosed in XTP Definition 3.5, 1991m "Appendix A: Check Function," Protocol Engines Inc., 1421 State Street, Santa Barbara, Calif. 93101.
It is an object of the present invention to provide an error detection code which overcomes the shortcomings of the prior art error correction codes. More specifically, it is an object of the invention to provide an error detection code which has powerful error detection properties (i.e., large d, b, k for a given h) but also has a simple software and/or hardware implementation.